There is an increasing demand to protect data transmitted over open networks such as the Internet and wireless communication networks. The Advanced Encryption Standard (AES) provides a scheme for encrypting and decrypting information that is growing in popularity. AES is a symmetric key approach in which both the sender and the receiver use the same key to encrypt and decrypt information.
Hardware implementations of AES provide advantages over software implementations. In software, the key is vulnerable to attack, and software implementations are not fast enough for Internet applications. In hardware, parallel processing and pipelining can be used to increase throughput and reduce latency. Furthermore, hardware implementations are considered more secure because tampering by an outside attacker is more difficult.
A switch box or substitution table (S-box) receives some number of bits as input, and returns some number of bits as output. The AES S-box includes a multiplicative inversion and an affine transformation. The inversion can be implemented using a 256-entry lookup table (LUT).
A Galois field (GF), or finite field, is a mathematical structure that is extensively used in fields such as cryptography. It is well known that a finite field of qn elements can be represented by polynomials modulo an irreducible polynomial of degree n, the polynomials being defined over GF(q). A field with 2mn elements can be represented either by an irreducible polynomial over GF(2) of degree mn, or as a composite field (or subfield) representation by an irreducible polynomial over GF(2n) of degree m.
By converting or transforming the basis of the original field to the composite or subfield representation, the inversion in the S-box can be simplified. Specifically, the inversion in GF(256) can be converted to calculations in GF(16)2, using an irreducible generating polynomial of the form x2+x+B, with B in GF(16). The inversion can then be implemented using a relatively small 16-entry LUT, thereby improving performance by increasing throughput and reducing latency through the hardware.
Conventionally, the AES S-box utilizes a large number of gates and dominates the hardware complexity of an AES circuit. As a result, conventional AES circuits have a high area overhead (that is, more area in silicon is required) and higher fabrication costs.
Accordingly, an AES S-box implementation that reduces gate count while maintaining high throughput would be advantageous. Embodiments in accordance with the present invention provide these and other advantages.